package com.lun.medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PopulatingNextRightPointersInEachNode {

	public static class Node {
		public int val;
		public Node left;
		public Node right;
		public Node next;

		public Node() {
		}

		public Node(int _val) {
			val = _val;
		}

		public Node(int _val, Node _left, Node _right, Node _next) {
			val = _val;
			left = _left;
			right = _right;
			next = _next;
		}
	};

	// 方法一：DFS
	public Node connect(Node root) {
		if (root == null)
			return root;
		connect(root, 0, new ArrayList<>());
		return root;
	}

	private void connect(Node node, int level, List<Node> prevs) {
		if (node == null)
			return;

		if (prevs.size() == level) {
			prevs.add(node);
		} else {
			Node prev = prevs.get(level);
			prev.next = node;
			prevs.set(level, node);
		}

		connect(node.left, level + 1, prevs);
		connect(node.right, level + 1, prevs);
	}

	// 方法二：BFS
	public Node connect2(Node root) {
		if (root == null)
			return root;

		LinkedList<Node> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {

			Node prev = null;
			for (int size = queue.size(); size > 0; size--) {
				Node node = queue.poll();

				if (prev != null) {
					prev.next = node;
				}

				prev = node;
				if (node.left != null)
					queue.offer(node.left);

				if (node.right != null)
					queue.offer(node.right);
			}
		}

		return root;
	}

	// 方法三：利用父节点的next
	public Node connect3(Node root) {
		if (root == null)
			return null;

		Node pre = root;
		Node cur = null;

		while (pre.left != null) {

			cur = pre;

			while (cur != null) {
				if (cur.left != null)
					cur.left.next = cur.right;

				if (cur.right != null && cur.next != null)
					cur.right.next = cur.next.left;

				cur = cur.next;
			}

			pre = pre.left;
		}

		return root;
	}
	

}
